'''
https://leetcode.cn/problems/longest-substring-with-at-most-k-distinct-characters
'''
from collections import Counter


class Solution:
    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
        n = len(s)
        n_char = 0
        cnt = Counter()
        l, r = 0, 0
        res = 0
        while l < n:
            while r < n and n_char <= k:
                cnt[s[r]] += 1
                if cnt[s[r]] == 1:
                    n_char += 1
                r += 1
            if n_char > k:
                res = max(res, r - l -1)
            else:
                res = max(res, r - l)
            cnt[s[l]] -= 1
            if cnt[s[l]] == 0:
                n_char -= 1
            l += 1
        return res

# s = 'eceba'
# k = 2
# s = 'aa'
# k = 1
s = 'abee'
k = 1
print(Solution().lengthOfLongestSubstringKDistinct(s, k))

